import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Test {
    public static void main4(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(1);
        Deque<Integer> stack = new LinkedList<>();//底层是一个链表 链式栈
        stack.push(10);
        Deque<Integer> stack2 = new ArrayDeque<>();//底层是一个数组 顺序栈

    }


    public static void main3(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(1);
        myQueue.offer(2);
        int val = myQueue.poll();
        System.out.println(val);
        int val2 = myQueue.peek();
        System.out.println(val2);
    }


    //力扣：最小栈
    
   /* Stack<Integer> stack;
    Stack<Integer> minStack;
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        //判断一下此时stack栈当中有没有数据
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        } else {
            if(val <= minStack.peek()) {
                minStack.push(val);
            }
        }
    }

    public void pop() {
        if(stack.empty()) {
            return;
        } else {
            int val = stack.pop();
            if(val == minStack.peek()) {
                minStack.pop();
            }
        }

    }

    public int top() {
        if(stack.empty()) {
            return -1;
        }
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }*/

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *牛客： 栈的压入、弹出序列
     * @param pushV int整型一维数组
     * @param popV int整型一维数组
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);//将数组中的元素放入到栈当中
            //因为可能弹出很多个，所以不能够使用if，应该使用while
            while(!stack.empty() && j < pushV.length &&stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
    public static void main2(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println("===========");
        System.out.println(myStack.pop());//4
        System.out.println(myStack.pop());//3
        System.out.println(myStack.pop());//2
        System.out.println(myStack.pop());//1
        System.out.println("=============");
        System.out.println(myStack.peek());

    }

    public static void main1(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(12);//push放入一个元素
        stack.push(23);
        stack.push(34);

        int x = stack.pop();//pop弹出一个元素(相当于删除栈顶元素）
        System.out.println(x);

        //peek获取当前栈顶元素,但是不删除
        int x2 = stack.peek();
        System.out.println(x2);

        //empty检查栈是否为空
        System.out.println(stack.empty());

        //ArrayDequeue可以代替栈


    }
    //逆波拉表达式(后缀表达式)求值
}
//力扣：有效的括号
class Solution1 {
    public boolean isValid(String s) {
        //用来存放左括号的栈
        Stack<Character> stack = new Stack<Character>();
        //遍历数组
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
//左括号的放入到栈当中
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                //右括号的，与栈中是否匹配
                if (stack.empty()) {
                    //empty 为空返回true
                    return false;
                } else {
                    char tmp = stack.peek();
                    if (ch == ')' && tmp == '(' || ch == '}' && tmp == '{' || ch == ']' && tmp == '[') {
                        stack.pop();//栈中的括号有与之匹配的我们就将左括号弹出栈
                    } else {
                        //有不匹配的就是无效的
                        return false;
                    }
                }
            }
        }
        //遍历完字符串之后可能栈中还有左括号
        if (!stack.empty()) {
            return false;
        } else {
            return true;
        }
    }
}

//力扣：逆波兰表达式求值
class Solution2 {
    public int evalRPN(String[] tokens) {
        //创建一个栈，将这些字符串放入到栈当中
        Stack<Integer> stack = new Stack<>();

        //for-each循环来将这些东西放入到栈当中
        for(String s : tokens) {
            //需要进行判断，当这些数据为整型时才放入到栈当中
            if(!isOpera(s)) {
                //Integer.parseInt(s);//将字符串转化为整数
                stack.push(Integer.parseInt(s));
            } else {//为运算符时
                int num2 = stack.pop();//最先弹出来的为右操作数
                int num1 = stack.pop();//第二个弹出来的为左操作数
                switch(s) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    //判断是否为运算符
    public boolean isOpera(String x) {
        if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/")) {
            return true;
        }
        return false;
    }
}
